package h_10_25;

import java.util.Arrays;

/**
 * 3634. 使数组平衡的最少移除数目
 * https://leetcode.cn/problems/minimum-removals-to-balance-array/description/
 */
public class Main4 {
    public int minRemoval(int[] nums, int k) {
        // 只关心最后的最大值和最小值，不关心顺序，那么进行排序，可以快速的算出
        // 排序
        Arrays.sort(nums);
        int left = 0;
        int right = 0;
        int maxSave = 0;
        int n = nums.length;
        while(right < n) {
            // 入  出
            while((long) nums[left] * k < nums[right]) {
                left++;
            }

            // 更
            maxSave = Math.max(maxSave,right - left + 1);
            right++;
        }

        // 用整个数组 - 需要的即是 需要删除的个数
        return n - maxSave;
    }
}
